/*
 * @lc app=leetcode.cn id=139 lang=cpp
 * @lcpr version=30204
 *
 * [139] 单词拆分
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution
{
public:
    bool wordBreak(string s, vector<string> &wordDict)
    {
        // 方法一：
        // unordered_set<string> wordSet(wordDict.begin(), wordDict.end()); // 将字典存入哈希表
        // vector<bool> dp(s.size() + 1, false); // dp[i] 表示 s[0:i] 是否可以被拼接
        // dp[0] = true; // 空字符串可以被拼接

        // for (int i = 1; i <= s.size(); ++i) {
        //     for (int j = 0; j < i; ++j) {
        //         if (dp[j] && wordSet.count(s.substr(j, i - j))) { // 检查 s[j:i] 是否在字典中
        //             dp[i] = true;
        //             break; // 一旦找到可行的拼接方式，停止内层循环
        //         }
        //     }
        // }

        // return dp[s.size()]; // 返回整个字符串是否可以被拼接

        // 方法二：
        int n = s.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        for (int i = 1; i <= n; ++i)
        {
            for (auto str : wordDict)
            {
                if (i >= str.size() && dp[i - str.size()] && s.substr(i - str.size(), str.size()) == str)
                {
                    dp[i] = true;
                    break; // 一旦找到匹配的单词，停止检查
                }
            }
            return dp[n];
        }
    }
};
// @lc code=end

/*
// @lcpr case=start
// "leetcode"\n["leet", "code"]\n
// @lcpr case=end

// @lcpr case=start
// "applepenapple"\n["apple", "pen"]\n
// @lcpr case=end

// @lcpr case=start
// "catsandog"\n["cats", "dog", "sand", "and", "cat"]\n
// @lcpr case=end

 */
